package com.kevinkk.tree;

/**
 * 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。
 * 修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
 */

/**
 * 修剪一个 BST 时，如果一个节点的值不在 [low, high] 之间，不应该直接删除这个元素
 * 这样的话连通其所有的子节点都会被删除
 * 而是，如果一个节点小于 low，那还要递归的去检查起右子树；同样的，如果一个节点大于 high，那还要递归的去检查其左子树
 */
public class TrimABinarySearchTree {
    class Solution {
        public TreeNode trimBST(TreeNode root, int low, int high) {
            if (root == null) return null;
            if (root.val < low) return trimBST(root.right, low, high);
            if (root.val > high) return trimBST(root.left, low, high);
            // 如果节点的值符合要求，那么递归的去检查其左右子树，不用删除该节点
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
            return root;
        }
    }
}
